package com.itheima.algorithm.binarysearch;

public class BinarySearch {

    //二分查找基础写法
    public static int binarySearchBasic(int [] a,int target){
        //i到j中存在值
        int i=0,j=a.length-1;
        while(i<=j){
            int m=(i+j)/2;
            if(target<a[m]){
                j=m-1;
            }else if(a[m]<target){
                i=m+1;
            }else{
                return m;
            }
        }
        return -1;
    }

    //二分查找改进写法
    public static int  binarySearchAlternative(int [] a,int target){
        int i=0,j=a.length;
        while(i<j){
            int m=(i+j)>>>1;
            if(target<a[m]){
                j=m;
            }else if(a[m]<target){
                i=m+1;
            }else{
                return m;
            }
        }
        return -1;
    }

    //平衡版
    public static int binarySearchBalance(int [] a,int target){
        int i=0,j=a.length;
        //还剩一个i的时候退出循环
        while(1<j-i){
            int m=(i+j)>>>1;
            if(target<a[m]){
                j=m;
            }else{
                i=m;
            }
        }
        if(a[i]==target){
            return i;
        }else{
            return-1;
        }
    }

    public static int binarySearchLeftmost1(int [] a,int target){
       int i=0,j=a.length-1;
       //最终值，没找到默认-1
       int candidate=-1;
       while(i<=j) {
           int m = (i + j) >>> 1;
           if (target < a[m]) {
               j = m - 1;
           } else if (a[m] < target) {
               i = m + 1;
           } else {
               //找到了，先记录下来
               candidate = m;
               //在去左侧找找
               j = m - 1;
           }
       }
           return candidate;
    }

    public static int binarySearchRightmost1(int [] a,int target){
        int i=0,j=a.length-1;
        //最终值，没找到默认-1
        int candidate=-1;
        while(i<=j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                //找到了，先记录下来
                candidate = m;
                //在去右侧找找
                i = m + 1;
            }
        }
        return candidate;
    }

    //返回>=target最左侧的值
    public static int binarySearchLeftmost2(int [] a,int target){
        int i=0,j=a.length-1;
        while(i<=j){
            int m=(i+j)>>>1;
            if(target<=a[m]){
                j=m-1;
            }else{
                i=m+1;
            }
        }
        return i;
    }

    //返回<=target最靠右的值
    public static int binarySearchRightmost2(int [] a,int target){
        int i=0,j=a.length-1;
        while(i<=j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i-1;
    }
}
